import numpy as np
from util import *
import copy
import pickle
import pymetis
from pymetis import Options 
import scipy.sparse as sp
from itertools import cycle
import random
# import hashlib
# import torch
import json
import os
import math
from Method.GA_for_ours_deploy import GA_algorithm
from Method.Heuristic_init_deploy import Heuristic_algorithm
from collections import Counter
from numpy.polynomial import polynomial as P
#在算法层面，不知道即将调度的task的dealing time和他的子任务数量


class OurMethod:
    def __init__(self,cloud_system):
        
        self.cloud_system=cloud_system
        self.env=cloud_system.env
        self.print_level=cloud_system.print_level
        self.state_resource_percent=self.cloud_system.args.state_resource_percent
        
        ####################################
        
        #记录结束工作的时间
        self.ms_obj_to_end_time={}
        self.remove_process=None
        self.base_method=None
        return
        
    def init_deploy(self):
        if self.cloud_system.args.elastic_deploy==True:
            if self.cloud_system.args.pre_deploy==True:
                self.init_deploy_with_Heuristic()
        else:
            #不弹性部署，则每类微服务部署一个，后续不进行微服务部署
            system_ms_kind_list=self.cloud_system.ms_kind_list
            for ms_kind in system_ms_kind_list:
                self.schedule_deploy_one_ms(ms_kind, None, without_cold_start=True)
                
            assert len(system_ms_kind_list)==len(self.ms_obj_to_end_time.keys())
        
    def schedule_deploy_one_ms(self, ms_kind, aim_node, without_cold_start=False):
        #获取冷启动时间
        if without_cold_start==True:
            cold_start_time=0
        else:
            cold_start_time=self.cloud_system.get_cold_start_time(ms_kind)
            
        if aim_node!=None:
            flage, ms_obj=aim_node.deploy_ms(ms_kind,without_cold_start=without_cold_start)
        else:
            flage=False
            
        if flage==True:
            #初始化的时候设置为冷启动结束时间
            self.set_ms_obj_end_time(ms_obj, cold_start_time)
            return ms_obj
        else:
            node_num=self.cloud_system.args.bare_metal_node_num
            node_index_list=random.sample(range(node_num), node_num)
            for node_index in node_index_list:
                node=self.cloud_system.bare_metal_node_list[node_index]
                flage, ms_obj =node.deploy_ms(ms_kind, without_cold_start=without_cold_start)
                if flage==True:
                    #初始化的时候设置为冷启动结束时间
                    self.set_ms_obj_end_time(ms_obj, cold_start_time)
                    return ms_obj
        
        print(f"schedule_random_deploy error (capacity lack)!")
        exit(-1)
        
    def init_deploy_with_Heuristic(self):
        
        if self.cloud_system.print_level>1:
            print("get init deploy strategy...")
        system_ms_kind_list=self.cloud_system.ms_kind_list
        weight_matrix_t = self.get_weight_matrix(system_ms_kind_list,direct_flage=True)
        
        cpu_cost_t = []
        mem_cost_t = []
        disk_cost_t = []
        for ms_kind in system_ms_kind_list:
            cpu_cost_t.append(self.cloud_system.ms_kind_to_resource_need[ms_kind]["cpu"])
            mem_cost_t.append(self.cloud_system.ms_kind_to_resource_need[ms_kind]["mem"])
            disk_cost_t.append(self.cloud_system.ms_kind_to_resource_need[ms_kind]["disk"])
        cpu_cost_t = np.array(cpu_cost_t)
        mem_cost_t = np.array(mem_cost_t)
        disk_cost_t = np.array(disk_cost_t)
        ms_ratio_t = np.sum(weight_matrix_t, axis=1) / np.sum(weight_matrix_t)
        node_num_t = self.cloud_system.args.bare_metal_node_num
        if self.cloud_system.print_level>1:
            print("start Heuristic...")
        
        spec_ms_kind_list_t, spec_node_index_list=Heuristic_algorithm(self.cloud_system.args.our_method_plan_file, system_ms_kind_list,weight_matrix_t, cpu_cost_t, mem_cost_t, disk_cost_t, ms_ratio_t, node_num_t, self.state_resource_percent, self.cloud_system.args.heuristic_deploy)
        self.cloud_system.pre_deploy_ms_number=len(spec_ms_kind_list_t)
        if self.cloud_system.print_level>1:
            print(f"微服务总数：{len(spec_ms_kind_list_t)},\n每类数量：{Counter(spec_ms_kind_list_t)}\n微服务详细信息：{spec_ms_kind_list_t}")
            print(f"各个节点上微服务数量：{Counter(spec_node_index_list)}\n对应node ID{spec_node_index_list}")
        
        spec_ms_kind_list=[]
        #需要进行类型转换
        for index in spec_ms_kind_list_t:
            spec_ms_kind_list.append(system_ms_kind_list[index])

        if self.cloud_system.print_level>1:
            print("end init strategy!")
        self.execute_init_deploy(spec_ms_kind_list, spec_node_index_list)
        
        return
    
    def get_weight_matrix(self, system_ms_kind_list, direct_flage=False):
        #基于类型，统计邻接矩阵
        ms_kind_adj=np.zeros((len(system_ms_kind_list), len(system_ms_kind_list)))
        for service_name in self.cloud_system.service_to_callgraph_dict.keys():
            request_t=self.cloud_system.service_to_callgraph_dict[service_name]
            for task_t in request_t.start_task_list:
                self.get_weight_matrix_update(task_t, ms_kind_adj, system_ms_kind_list, direct_flage)
        return ms_kind_adj
        
    def get_weight_matrix_update(self,task, ms_kind_adj, system_ms_kind_list, direct_flage):
        for sub_task in task.sub_task_list:
            task_index=system_ms_kind_list.index(task.ms_kind)
            sub_task_index=system_ms_kind_list.index(sub_task.ms_kind)
            call_num=sub_task.call_num
            ms_kind_adj[task_index][sub_task_index]+=call_num
            if direct_flage==False:  #代表是否区分调用方向，false则表示不区分
                ms_kind_adj[sub_task_index][task_index]+=call_num
            self.get_weight_matrix_update(sub_task, ms_kind_adj, system_ms_kind_list, direct_flage)
        


    
    
    
    def execute_init_deploy(self, ms_kind_list, node_index_list):
        #这里输入的ms_kind_list和cloud system 中的不一样，这里的可以重复，而cloud system中的不可以重复
        
        #根据社团划分结果进行部署
        for index in range(len(ms_kind_list)):
            ms_kind=ms_kind_list[index]
            node_index=node_index_list[index]
            result, ms_obj= self.cloud_system.bare_metal_node_list[node_index].deploy_ms(ms_kind, without_cold_start=True)
            
            assert result==True
            #常驻微服务，中途不会被删除
            ms_obj.stable_flage_for_ours=True
            
            # self.set_ms_obj_end_time(ms_obj, 0)
        
        
    
    def set_ms_obj_end_time(self, ms_obj, end_time):
        self.ms_obj_to_end_time[ms_obj]=end_time
        return
    
    def update_ms_obj_end_time(self, ms_obj):
        estimate_end_time=ms_obj.get_estimate_end_time()
        self.ms_obj_to_end_time[ms_obj]=estimate_end_time
        return estimate_end_time
    
    def get_ms_obj_end_time(self, ms_obj):
        return self.ms_obj_to_end_time[ms_obj]
    
    def rm_ms_obj_end_time(self, ms_obj):
        del self.ms_obj_to_end_time[ms_obj]
    #######################################################################################
    #入口函数
    def do_schedule_deploy(self):
        if self.cloud_system.args.dynamic_replica==False:
            self.base_method.do_schedule_deploy()
        else:
            #我们的调度方法
            not_scheduled_tasks=[]
            for task in self.cloud_system.pending_task_queue:
                if task.request.request_base==None:
                    #获取模板request对象
                    base_request=self.cloud_system.service_to_callgraph_dict[task.request.service_name]
                    #拷贝一份request模板给task的request
                    task.request.set_deepcopy_request_base(base_request)
                    #更新start_task_list
                    # task.request.request_base.update_base_start_task_list(task)
                    #赋值可靠性和deadline
                    # task.request.request_base.reset_for_our_method(task.request.reliability)
                    task.request.add_attribute_for_our_method()
                    # for task_t in task.request.request_base.task_id_to_obj.values():
                    #     task.request.request_base.
                
                spec_request_base=task.request.request_base
                task_base=spec_request_base.task_id_to_obj[task.task_id]
                task.ave_deal_time=task_base.ave_deal_time
                # print("start getting replica num")
                replica_num=self.schedule_get_replica(task.request, task_base)
                # print("end getting replcia num")
                assert replica_num!=None
                task.set_replica_num(replica_num)
                result=self.schedule_ours_deploy_and_select_ms(task, replica_num, task_base)
                #说明调度失败
                if result==False:
                    not_scheduled_tasks.append(task)
                    if self.print_level>10:
                        print(f"Time:{round(self.env.now)}\t (SCHE FAILED EVENT) \t{task.request.request_id}\t{task.task_id}")
                # else:
                #     task.request.request_base.scheduled_task_list.append(task)
                    
            #清空队列
            self.cloud_system.pending_task_queue=not_scheduled_tasks
            if self.cloud_system.args.elastic_deploy==True:
                self.reset_ms_remove_event()
        return 
    
    
    #为task选择微服务或者部署新的微服务
    def schedule_ours_deploy_and_select_ms(self, task, replica_num, task_base):
        #获取现在的时间
        time_now=self.cloud_system.env.now
        task.ave_deal_time=task_base.ave_deal_time
        #获取所有正在运行的微服务列表
        ms_obj_list=self.cloud_system.get_available_ms_obj_with_ms_kind(task.ms_kind)
        ms_obj_with_early_start_time_list=[]
        for ms_obj in ms_obj_list:
            #更新最早开始时间
            ms_idle_time=self.update_ms_obj_end_time(ms_obj)   #都是绝对时间
            TT=self.cloud_system.get_TT_time(task, ms_obj, task.first_parent_ms_obj)
            early_start_time=max(time_now+TT, ms_idle_time)
            ms_obj_with_early_start_time_list.append([early_start_time, ms_obj])
        #记录父微服务，用于计算数据传输时间
        if task.parent_task==None:
            parent_ms=None
        else:
            parent_ms=task.parent_task.first_parent_ms_obj
        ##调度到微服务上
        for index in range(replica_num):
            if self.cloud_system.args.elastic_deploy==True and self.judge_need_new_ms(task, task_base, ms_obj_with_early_start_time_list):
                #部署新的微服务并调度task过去
                ms_obj_new=self.schedule_ours_deploy(parent_ms, task.ms_kind)
                #需要排除无法部署的情况
                if ms_obj_new==None:
                    if index == 0:   #刚开始部署就失败，则调度失败，直接返回
                        return False
                    else:
                        #说明已经部署过至少一次了，可以重复放到同一个MS上
                        assert len(ms_obj_with_early_start_time_list)>0
                        [early_start_time, ms_obj_new]=ms_obj_with_early_start_time_list[0]
                        
                TT_new=self.cloud_system.get_TT_time(task, ms_obj_new, task.first_parent_ms_obj)
                early_start_time_new=max(time_now+TT_new, self.ms_obj_to_end_time[ms_obj_new])
                self.set_ms_obj_end_time(ms_obj_new, early_start_time_new+task_base.ave_deal_time)
                self.cloud_system.env.process(ms_obj_new.put_task_to_queue_event(task))
                #这里面存的应该是下一个任务的最早开始时间，需要加上TT传输时间
                ms_obj_with_early_start_time_list.append([early_start_time_new+task_base.ave_deal_time, ms_obj_new])
                task.aim_ms_obj_list.append(ms_obj_new)
                continue
                
            ms_obj_with_early_start_time_list.sort(key=lambda x:x[0])
            [early_start_time, aim_ms]=ms_obj_with_early_start_time_list[0]
            plan_end_time=early_start_time+task_base.ave_deal_time
            self.set_ms_obj_end_time(aim_ms, plan_end_time)
            self.cloud_system.env.process(aim_ms.put_task_to_queue_event(task)) 
            ms_obj_with_early_start_time_list[0][0]+=task_base.ave_deal_time
            task.aim_ms_obj_list.append(aim_ms)
        return True
    
    def judge_need_new_ms(self, task, task_base, ms_obj_with_early_start_time_list):
        #需要新建 True， 不需要为False
        if len(ms_obj_with_early_start_time_list)==0:
            return True
        ms_obj_with_early_start_time_list.sort(key=lambda x:x[0])
        [early_start_time, aim_ms]=ms_obj_with_early_start_time_list[0]
        #如果新建的最早开始时间小于当前的最早开始时间，则重新创建一个(重新创建一个有冷启动时间)
        if early_start_time>self.env.now+self.cloud_system.get_cold_start_time(aim_ms.ms_kind):
            return True
        else:
            return False
        
    #部署
    def schedule_ours_deploy(self, parent_ms, ms_kind):
        #优先在父微服务部署
        if parent_ms!=None:
            flage, ms_obj =parent_ms.node_obj.deploy_ms(ms_kind)
            if flage==True:
                self.set_ms_obj_end_time(ms_obj, self.env.now+self.cloud_system.get_cold_start_time(ms_kind))
                return ms_obj
        node_num=self.cloud_system.args.bare_metal_node_num
        node_index_list=random.sample(range(node_num), node_num)
        for node_index in node_index_list:
            node=self.cloud_system.bare_metal_node_list[node_index]
            # msid_list=node.msid_to_msobj.keys()
            # for ms_id in msid_list:
                # if node.msid_to_msobj[ms_id].ms_kind!=ms_kind and node.msid_to_msobj[ms_id].can_be_rm():
                #     node.remove_ms(ms_id)
            flage, ms_obj =node.deploy_ms(ms_kind)
            if flage==False:
                continue
            # assert flage==True
            #初始化的时候设置为冷启动结束时间
            self.set_ms_obj_end_time(ms_obj, self.env.now+self.cloud_system.get_cold_start_time(ms_kind))
            return ms_obj
        
        return None
        
    
    def reset_ms_remove_event(self):
        try:
            self.remove_process.interrupt()
        except:
            pass
            
        if len(self.ms_obj_to_end_time.keys())>0:
            sorted_keys=sorted(self.ms_obj_to_end_time, key=lambda k:self.ms_obj_to_end_time[k])
            #寻找第一个非常驻微服务
            self.next_remove_ms=None
            for index in range(len(sorted_keys)):
                if sorted_keys[index].stable_flage_for_ours==False:
                    self.next_remove_ms=sorted_keys[index]
                    break
            if self.next_remove_ms==None:
                return
            else:
                interval=max(0, self.ms_obj_to_end_time[self.next_remove_ms]-self.cloud_system.env.now)
                self.remove_process=self.cloud_system.env.process(self.remove_latest_end_ms_obj(interval))
        
    def remove_latest_end_ms_obj(self, interval):
        try:
            yield self.cloud_system.env.timeout(interval)
            if self.next_remove_ms!=None:
                #先删除之前确定的需要删除的微服务
                if self.next_remove_ms.can_be_rm():
                    self.next_remove_ms.node_obj.remove_ms(self.next_remove_ms.ms_id)
                    self.rm_ms_obj_end_time(self.next_remove_ms)
                else:
                    self.ms_obj_to_end_time[self.next_remove_ms]+=100
            
            if len(self.ms_obj_to_end_time.keys())>0:
                sorted_keys=sorted(self.ms_obj_to_end_time, key=lambda k:self.ms_obj_to_end_time[k])
                #寻找第一个非常驻微服务
                self.next_remove_ms=None
                for index in range(len(sorted_keys)):
                    if sorted_keys[index].stable_flage_for_ours==False:
                        self.next_remove_ms=sorted_keys[index]
                        break
                if self.next_remove_ms==None:
                    return
                else:
                    interval=max(0, self.ms_obj_to_end_time[self.next_remove_ms]-self.cloud_system.env.now)
                    self.remove_process=self.cloud_system.env.process(self.remove_latest_end_ms_obj(interval))
            else:
                self.remove_process=None
                
        except:
            pass
        return
    
        
    def schedule_get_replica(self, this_request, task_base):
        if task_base.replica_num!=None:
            return task_base.replica_num
        
        if task_base in this_request.front_task_list:
            this_request.front_task_list.remove(task_base)
        for sub_task in task_base.sub_task_list:
            this_request.front_task_list.append(sub_task)
        prob_list=[]
        for task in this_request.front_task_list:
            prob_list.append(task.call_num/task.parent_task.call_num)
        reliability_req=this_request.reliability/this_request.already_reliability
        # print(f"prob:{prob_list}\n")
        # prob_list=[]
        if len(prob_list)==0:
            solution=[reliability_req]
        else:
            # #计算多项式系数
            # coefficients=self.calculate_independent_event_probabilities(prob_list)
            
            # coefficients.insert(0, reliability_req*(-1))
            # # print(f"cofficient:{coefficients}\n")
            # solution = self.solve_multivariable_linear_equation(coefficients)
            
            solution=self.get_single_reliability_by_full_bayes(reliability_req,prob_list)
            
        
        assert len(solution)==1
        
        #获取指定微服务故障参数
        ms_lambda=self.cloud_system.ms_kind_to_transient_lambda[task_base.ms_kind]
        #获取单个task无故障概率
        single_reliability=self.get_reliability_without_failure(task_base.ave_deal_time, ms_lambda)
        replica_num=self.get_aim_replica_num(solution[0], single_reliability)
        task_base.replica_num=replica_num
        this_request.already_reliability=this_request.already_reliability*(1-math.pow(1-single_reliability, replica_num))
        
        return replica_num
        
    
    def get_single_reliability_by_full_bayes(self, reliability_req, probability_list):
        max_value=1
        min_value=reliability_req
        ave_value=(max_value+min_value)/2
        precision=0.00000000001
        while max_value-min_value>precision:
            func_value=self.get_func_value(probability_list,ave_value)-reliability_req
            if func_value>0:
                max_value=ave_value
            else:
                min_value=ave_value
            ave_value=(max_value+min_value)/2
        return [ave_value]
    
    
    def get_func_value(self, probability_list,R):
        value=R
        for prob in probability_list:
            value*=(1-prob+prob*R)
        return R
        
        
        
        
        #这是被立即执行删除的动作，由微服务本身触发
    def ms_complete_and_can_be_rm(self, ms_obj):
        if self.cloud_system.args.dynamic_replica==False:
            self.base_method.ms_complete_and_can_be_rm(ms_obj)
        else:
            del self.ms_obj_to_end_time[ms_obj]
            ms_obj.node_obj.remove_ms(ms_obj.ms_id)
            
            if self.next_remove_ms.ms_id==ms_obj.ms_id:
                self.reset_ms_remove_event()
    
    def calculate_independent_event_probabilities(self, probabilities):
        """
        计算给定独立事件的概率列表，返回每个事件发生的概率列表。
        
        Args:
            probabilities: 一个概率列表，其中 probabilities[i] 是第 i 个事件发生的概率。
            
        Returns:
            A list of probabilities, where result[i] is the probability of exactly i events occurring .
        """
        N = len(probabilities)
        result = [0.0] * (N + 1)

        # 计算0个事件发生的概率 (即所有事件都不发生)
        no_event_prob = 1.0
        for p in probabilities:
            no_event_prob *= (1 - p)
        result=[no_event_prob,1-no_event_prob]
        # result.reverse()
        return result
        
        result[0] = no_event_prob

        # 使用每个事件的概率计算1到N个事件发生的概率
        for i in range(1, N + 1):
            # 计算i个事件发生的概率（i个事件中的组合）
            event_probability = 0.0

            # 计算所有的组合
            from itertools import combinations
            for combo in combinations(range(N), i):
                # combo包含的是第i个事件发生的索引
                prob = 1.0
                for j in range(N):
                    if j in combo:
                        prob *= probabilities[j]  # 事件发生的概率
                    else:
                        prob *= (1 - probabilities[j])  # 事件不发生的概率
                event_probability += prob

            result[i] = event_probability
        # result.reverse()
        return result
    

    def solve_multivariable_linear_equation(self, coefficients):
        
        # roots = np.roots(coefficients)
        roots=P.polyroots(coefficients)

        # 筛选出在 [0, 1] 范围内的实数解
        valid_solutions = [r.real for r in roots if np.isreal(r) and 0 <= r.real <= 1]
        return valid_solutions
    
    def get_reliability_without_failure(self, duration, lambda_t):
        reliability=math.exp(-1*duration*lambda_t)
        return reliability
    
    def get_aim_replica_num(self, aim_reliability, single_reliability):
        aim_replica_num=1
        while 1-(1-single_reliability)**aim_replica_num <aim_reliability:
            aim_replica_num+=1
        return aim_replica_num